package chapter20;

/**
 * vanEmdeBoas树-原型vEB树
 * <p>
 * 支持优先队列操作以及一些其他操作，每个操作最坏情况运行时间为O(lglgn)
 * 限制关键字必须为0~n-1的整数且不重复
 * <p>
 * 特征：
 * 1.如果u=2，那么它是基础大小，只包含一个两个位的数组A[0..1]
 * 2.否则，对某个整数k>=1,u=2^(2^k),于是有u>=4。除了全域大小u之外：
 * * a.一个名为summary的指针，指向一个 proto-vEB(√u)结构
 * * b.一个数组cluster[1..(√u-1)],存储√u个指针，每个指针指向一个proto-vEB(√u)结构
 */
public class Proto_vEB {

    public static int member(P_vEB V, int x) {
        if (V.u == 2) {
            return V.A[x];
        } else {
            return member(V.cluster[high(V, x)], low(V, x));
        }
    }

    /**
     * 最大值是先看u==2的时候，
     * 先看A[0]是否为1，如果是1则返回下标0
     * 如果不唯一说明左分支没有值，则A[1]是否为1，如果是1则返回下标1
     */
    public static int minimum(P_vEB V) {
        if (V.u == 2) {
            if (V.A[0] == 1) {
                return 0;
            } else if (V.A[1] == 1) {
                return 1;
            } else {
                return -1;
            }
        } else {
            int minCluster = minimum(V.summary);
            if (minCluster == -1) {
                return -1;
            } else {
                int offset = minimum(V.cluster[minCluster]);
                return index(V, minCluster, offset);
            }
        }
    }

    /**
     * 最大值是先看u==2的时候，
     * 先看A[1]是否为1，如果是1则返回下标1
     * 如果不唯一说明右分支没有值，则A[0]是否为1，如果是1则返回下标0
     */
    public static int maximum(P_vEB V) {
        if (V.u == 2) {
            if (V.A[1] == 1) {
                return 1;
            } else if (V.A[0] == 1) {
                return 0;
            } else {
                return -1;
            }
        } else {
            int maxCluster = maximum(V.summary);
            if (maxCluster == -1) {
                return -1;
            } else {
                int offset = maximum(V.cluster[maxCluster]);
                return index(V, maxCluster, offset);
            }
        }
    }

    /**
     * 后继
     */
    public static int successor(P_vEB V, int x) {
        // 当u==2时候,x==0代表自己是当前簇的最小值,并且看右边A[1]=1证明大于x的存在,则返回坐标1
        if (V.u == 2) {
            if (x == 0 && V.A[1] == 1) {
                return 1;
            }
            return -1;
        } else {
            // 正常递归
            int offset = successor(V.cluster[high(V, x)], low(V, x));
            if (offset != -1) {
                // 如果不存在后继则以当前的x重新计算簇的位置
                return index(V, high(V, x), offset);
            } else {
                // 如果存在利用summary计算后继在哪个簇中
                int succCluster = successor(V.summary, high(V, x));
                // 如果后继簇不存在则返回-1
                if (succCluster == -1) {
                    return -1;
                } else {
                    // 存在后继簇则找出簇中最小值,为原始x的后继
                    offset = minimum(V.cluster[succCluster]);
                    // 计算并返回最小值
                    return index(V, succCluster, offset);
                }
            }
        }
    }

    /**
     * 前驱
     */
    public static int predecessor(P_vEB V, int x) {
        // 当u==2时候,x==1代表自己是当前簇的最大值,并且看右边A[0]=1证明大于x的存在,则返回坐标0
        if (V.u == 2) {
            if (x == 1 && V.A[0] == 1) {
                return 0;
            }
            return -1;
        } else {
            int offset = predecessor(V.cluster[high(V, x)], low(V, x));
            if (offset != -1) {
                return index(V, high(V, x), offset);
            } else {
                // 利用summary判断是否在整个簇中
                int preCluster = predecessor(V.summary, high(V, x));
                if (preCluster == -1) {
                    return -1;
                } else {
                    // 存在后继簇则找出簇中最大值,为原始x的前驱
                    offset = maximum(V.cluster[preCluster]);
                    return index(V, preCluster, offset);
                }
            }
        }
    }

    /**
     * 向V中插入x
     */
    public static void insert(P_vEB V, int x) {
        // 如果域是2,则将对应的数值位设置位1
        if (V.u == 2) {
            V.A[x] = 1;
        } else {
            // 插入cluster
            insert(V.cluster[high(V, x)], low(V, x));
            // 插入summary
            insert(V.summary, high(V, x));
        }
        // 元素数量+1
        V.n++;
    }

    /**
     * 删除一个x
     */
    public static void delete(P_vEB V, int x) {
        // 如果域是2,则将对应的数值位设置位0
        if (V.u == 2) {
            V.A[x] = 0;
        } else {
            // 删除cluster
            delete(V.cluster[high(V, x)], low(V, x));
            // 只有当当前节点元素数量位0才能去将summary的为0
            if (V.n == 0) {
                delete(V.summary, high(V, x));
            }
        }
        // 元素数量-1
        V.n--;
    }

    /**
     * 根据数据域的大小u，创建一个proto_vEB树
     */
    public static P_vEB createP_vEB(int u) {
        P_vEB V = new P_vEB();
        create(V, u);
        return V;
    }

    /**
     * 递归创建 proto_vEB树的结构
     */
    private static void create(P_vEB V, int u) {
        // u==2是最小的原子单位,会初始化需要存储的数据的数组A
        if (u == 2) {
            V.u = u;
            V.A = new int[u];
            return;
        }
        // 创建的 summary cluster 域的大小
        int u1 = (int) Math.sqrt(u);
        // 当前节点的域大小是原始的域大小
        V.u = u;
        // 递归创建 summary
        V.summary = new P_vEB();
        create(V.summary, u1);
        // 循环创建cluster里的每一个元素,然后递归初始化
        V.cluster = new P_vEB[u1];
        for (int i = 0; i < u1; i++) {
            V.cluster[i] = new P_vEB();
            create(V.cluster[i], u1);
        }
    }

    /**
     * x的簇号
     */
    private static int high(P_vEB V, int x) {
        return (int) (x / Math.sqrt(V.u));
    }

    /**
     * x在簇中自己的位置
     */
    private static int low(P_vEB V, int x) {
        return (int) (x % Math.sqrt(V.u));
    }

    /**
     * 从x和y中产生一个元素编号
     * x：元素编码中最高(lgu)/2位 high(x)
     * y：元素编码中最低(lgu)/2位 low(x)
     */
    private static int index(P_vEB V, int x, int y) {
        return (int) (x * Math.sqrt(V.u) + y);
    }

    public static class P_vEB {
        public int u;
        public P_vEB summary;
        public P_vEB[] cluster;
        public int[] A;
        public int n;
    }

}
